/**
 * 自下而顶的排序算法
 * 利用双层循环,将数组划分为最小单元
 * 在最小单元进行归并,自底向上进行排序
 * @author dc
 * @Classname MergeSortBu
 * @Date 2020/1/4 14:34
 */
public class MergeSortBu extends BaseSort{
    /**归并所需的辅助数组*/
    private static Comparable[] aux;

    public static void sort(Comparable[] a){
        int N=a.length;
        int mid;
        int hi;
        aux=new Comparable[N];
        //sz:子数组大小
        //1表示，一个一个的归并，归并后的长度为2,
        // 2表示两个两个的归并，归并后的长度为4,以此类推
        for(int sz=1;sz<N;sz=2*sz){
            //lo:子数组下表索引
            //按照sz的长度归并回a数组，归并后长度翻倍
            for(int lo=0;lo<N-sz;lo+=2*sz){
                mid = lo+sz-1;
                //对于数组长度不满足2的x次幂的数组，mid可能会大于end
                hi = Math.min(2*sz+lo-1,N-1);
                merge(a,lo,mid,hi);
            }
        }
    }

    /**
     * 原地归并抽象方法
     * 用于将两个不同的有序数组归并到第三个数组中
     * @param a 需要归并进入的原数组
     * @param lo   原数组第一个
     * @param mid  原数组中间
     * @param hi   原数组最后一个
     */
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        //将a[lo..mid]和a[mid+1...hi]两个拆分后有序数组进行归并
        int i=lo;
        int j=mid+1;
        //将原数组a[lo..hi]复制到aux[lo...hi]数组中
        for(int k=lo;k<=hi;k++){
            aux[k]=a[k];
        }
        for(int k=lo;k<=hi;k++){
            //将a[lo..mid]和a[mid+1...hi]归并回到a[lo...hi]中
            if(i>mid){
                //左半边数组a[lo...mid]取尽,直接取右边数组
                a[k]=aux[j++];
            }else if(j>hi){
                //右半边数组a[mid+1...hi]取尽,依次取左边数组
                a[k]=aux[i++];
            }else if(less(aux[j],aux[i])){
                //如果左边数组取出的元素小于右边取出的元素
                //则将右边数组的元素归并回原数组,并且指针后移
                a[k]=aux[j++];
            }else{
                //反之将左边数组的元素归并回原数组,并且指针后移
                a[k]=aux[i++];
            }
        }
    }
}
